package J20250121_Dynamic;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description: 动态规划23——26
 * User: 王圆豪
 * Date: 2025-01-21
 * Time: 23:33
 */
public class Solution {
    //环绕字符串中唯一的子字符串——https://leetcode.cn/problems/unique-substrings-in-wraparound-string/
    public int findSubstringInWraproundString(String s) {
        char[] ss = s.toCharArray();
        int m = s.length();
        int[] dp = new int[m];
        dp[0] = 1;
        int ret = 0;
        boolean[] hash = new boolean[26];
        hash[ss[0]-'a'] = true;
        for(int i = 1; i < m; i++){
            int pos = ss[i] - 'a';
            if(ss[i-1]==ss[i]-1 || (ss[i] == 'a' && ss[i-1] == 'z')){
                dp[i] += dp[i-1] + 1;
                dp[i-1] = 0;
            }else {
                dp[i] = dp[i-1];
                dp[i-1] = 0;
            }
            if(!hash[pos]) dp[i]++;
            hash[pos] = true;
        }
        for(int a : dp) ret += a;
        return ret;
    }
    //单词拆分——https://leetcode.cn/problems/word-break/
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        int m = s.length();
        boolean[] dp = new boolean[m+1];
        dp[0] = true;
        s = " " + s;

        for(int i = 1; i <= m; i++){
            for(int j = i; j >= 1; j--){
                if(dp[j-1] && set.contains(s.substring(j,i+1))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[m];
    }
    //等差数组的划分——https://leetcode.cn/problems/arithmetic-slices/
    public int numberOfArithmeticSlices(int[] nums) {
        int m = nums.length;
        int[] dp = new int[m];
        int ret = 0;
        for(int i = 2; i < m; i++){
            if(nums[i]-nums[i-1] == nums[i-1] - nums[i-2]){
                dp[i] = dp[i-1] + 1;
            }else dp[i] = 0;
            ret += dp[i];
        }
        return ret;
    }
    //最长湍流子数组——https://leetcode.cn/problems/longest-turbulent-subarray/
    public int maxTurbulenceSize(int[] arr) {
        int m = arr.length;
        int[] f = new int[m];
        int[] g = new int[m];
        f[0] = g[0] = 1;
        int ret = 1;
        for(int i = 1; i < m; i++){
            if(i % 2 == 1){
                if(arr[i] < arr[i-1]){
                    f[i] = f[i-1] + 1;
                    g[i] = 1;
                }
                else if(arr[i] > arr[i-1]){
                    g[i] = g[i-1] + 1;
                    f[i] = 1;
                }else{
                    g[i] = 1;
                    f[i] = 1;
                }
            }
            else{
                if(arr[i] < arr[i-1]){
                    g[i] = g[i-1] + 1;
                    f[i] = 1;
                }
                else if(arr[i] > arr[i-1]){
                    f[i] = f[i-1] + 1;
                    g[i] = 1;
                }else{
                    g[i] = 1;
                    f[i] = 1;
                }
            }
            ret = Math.max(Math.max(f[i],g[i]), ret);
        }
        return ret;
    }
}
